package leetcode.array;

/**
 * @Description: https://leetcode.cn/problems/product-of-array-except-self/description/
 * @Author Ammar
 * @Create 2023/8/4 19:04
 */
public class _238_除自身以外数组的乘积 {
    /**
     * 返回数组 answer 不算空间复杂度
     * 针对每个元素 i，题目的意思是求 i 的前缀乘积 * 后缀乘积
     * 前缀：i 前面的元素
     * 后缀：i 后面的元素
     */
    public int[] productExceptSelf(int[] nums) {
        int[] answer = new int[nums.length];
        answer[0] = 1;
        // answer 存储前缀元素的乘积
        for (int i = 1; i < answer.length; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }

        // 将前缀元素与后缀元素乘积相乘
        int r = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            r = r * nums[i + 1];
            answer[i] = answer[i] * r;
        }
        return answer;
    }
}
